home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / linux / bitmap.h < prev    next >
C/C++ Source or Header  |  2005-10-13  |  8KB  |  257 lines
  1. #ifndef __LINUX_BITMAP_H
  2. #define __LINUX_BITMAP_H
  3.  
  4. #ifdef __KERNEL__
  5. #ifndef __ASSEMBLY__
  6.  
  7. #include <linux/types.h>
  8. #include <linux/bitops.h>
  9. #include <linux/string.h>
  10.  
  11. /*
  12.  * bitmaps provide bit arrays that consume one or more unsigned
  13.  * longs.  The bitmap interface and available operations are listed
  14.  * here, in bitmap.h
  15.  *
  16.  * Function implementations generic to all architectures are in
  17.  * lib/bitmap.c.  Functions implementations that are architecture
  18.  * specific are in various include/asm-<arch>/bitops.h headers
  19.  * and other arch/<arch> specific files.
  20.  *
  21.  * See lib/bitmap.c for more details.
  22.  */
  23.  
  24. /*
  25.  * The available bitmap operations and their rough meaning in the
  26.  * case that the bitmap is a single unsigned long are thus:
  27.  *
  28.  * bitmap_zero(dst, nbits)            *dst = 0UL
  29.  * bitmap_fill(dst, nbits)            *dst = ~0UL
  30.  * bitmap_copy(dst, src, nbits)            *dst = *src
  31.  * bitmap_and(dst, src1, src2, nbits)        *dst = *src1 & *src2
  32.  * bitmap_or(dst, src1, src2, nbits)        *dst = *src1 | *src2
  33.  * bitmap_xor(dst, src1, src2, nbits)        *dst = *src1 ^ *src2
  34.  * bitmap_andnot(dst, src1, src2, nbits)    *dst = *src1 & ~(*src2)
  35.  * bitmap_complement(dst, src, nbits)        *dst = ~(*src)
  36.  * bitmap_equal(src1, src2, nbits)        Are *src1 and *src2 equal?
  37.  * bitmap_intersects(src1, src2, nbits)     Do *src1 and *src2 overlap?
  38.  * bitmap_subset(src1, src2, nbits)        Is *src1 a subset of *src2?
  39.  * bitmap_empty(src, nbits)            Are all bits zero in *src?
  40.  * bitmap_full(src, nbits)            Are all bits set in *src?
  41.  * bitmap_weight(src, nbits)            Hamming Weight: number set bits
  42.  * bitmap_shift_right(dst, src, n, nbits)    *dst = *src >> n
  43.  * bitmap_shift_left(dst, src, n, nbits)    *dst = *src << n
  44.  * bitmap_scnprintf(buf, len, src, nbits)    Print bitmap src to buf
  45.  * bitmap_parse(ubuf, ulen, dst, nbits)        Parse bitmap dst from buf
  46.  */
  47.  
  48. /*
  49.  * Also the following operations in asm/bitops.h apply to bitmaps.
  50.  *
  51.  * set_bit(bit, addr)            *addr |= bit
  52.  * clear_bit(bit, addr)            *addr &= ~bit
  53.  * change_bit(bit, addr)        *addr ^= bit
  54.  * test_bit(bit, addr)            Is bit set in *addr?
  55.  * test_and_set_bit(bit, addr)        Set bit and return old value
  56.  * test_and_clear_bit(bit, addr)    Clear bit and return old value
  57.  * test_and_change_bit(bit, addr)    Change bit and return old value
  58.  * find_first_zero_bit(addr, nbits)    Position first zero bit in *addr
  59.  * find_first_bit(addr, nbits)        Position first set bit in *addr
  60.  * find_next_zero_bit(addr, nbits, bit)    Position next zero bit in *addr >= bit
  61.  * find_next_bit(addr, nbits, bit)    Position next set bit in *addr >= bit
  62.  */
  63.  
  64. /*
  65.  * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
  66.  * to declare an array named 'name' of just enough unsigned longs to
  67.  * contain all bit positions from 0 to 'bits' - 1.
  68.  */
  69.  
  70. /*
  71.  * lib/bitmap.c provides these functions:
  72.  */
  73.  
  74. extern int __bitmap_empty(const unsigned long *bitmap, int bits);
  75. extern int __bitmap_full(const unsigned long *bitmap, int bits);
  76. extern int __bitmap_equal(const unsigned long *bitmap1,
  77.                     const unsigned long *bitmap2, int bits);
  78. extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
  79.             int bits);
  80. extern void __bitmap_shift_right(unsigned long *dst,
  81.                         const unsigned long *src, int shift, int bits);
  82. extern void __bitmap_shift_left(unsigned long *dst,
  83.                         const unsigned long *src, int shift, int bits);
  84. extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  85.             const unsigned long *bitmap2, int bits);
  86. extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  87.             const unsigned long *bitmap2, int bits);
  88. extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  89.             const unsigned long *bitmap2, int bits);
  90. extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  91.             const unsigned long *bitmap2, int bits);
  92. extern int __bitmap_intersects(const unsigned long *bitmap1,
  93.             const unsigned long *bitmap2, int bits);
  94. extern int __bitmap_subset(const unsigned long *bitmap1,
  95.             const unsigned long *bitmap2, int bits);
  96. extern int __bitmap_weight(const unsigned long *bitmap, int bits);
  97.  
  98. extern int bitmap_scnprintf(char *buf, unsigned int len,
  99.             const unsigned long *src, int nbits);
  100. extern int bitmap_parse(const char __user *ubuf, unsigned int ulen,
  101.             unsigned long *dst, int nbits);
  102. extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
  103. extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
  104. extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
  105.  
  106. #define BITMAP_LAST_WORD_MASK(nbits)                    \
  107. (                                    \
  108.     ((nbits) % BITS_PER_LONG) ?                    \
  109.         (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL        \
  110. )
  111.  
  112. static inline void bitmap_zero(unsigned long *dst, int nbits)
  113. {
  114.     if (nbits <= BITS_PER_LONG)
  115.         *dst = 0UL;
  116.     else {
  117.         int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  118.         memset(dst, 0, len);
  119.     }
  120. }
  121.  
  122. static inline void bitmap_fill(unsigned long *dst, int nbits)
  123. {
  124.     size_t nlongs = BITS_TO_LONGS(nbits);
  125.     if (nlongs > 1) {
  126.         int len = (nlongs - 1) * sizeof(unsigned long);
  127.         memset(dst, 0xff,  len);
  128.     }
  129.     dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
  130. }
  131.  
  132. static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
  133.             int nbits)
  134. {
  135.     if (nbits <= BITS_PER_LONG)
  136.         *dst = *src;
  137.     else {
  138.         int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  139.         memcpy(dst, src, len);
  140.     }
  141. }
  142.  
  143. static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
  144.             const unsigned long *src2, int nbits)
  145. {
  146.     if (nbits <= BITS_PER_LONG)
  147.         *dst = *src1 & *src2;
  148.     else
  149.         __bitmap_and(dst, src1, src2, nbits);
  150. }
  151.  
  152. static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  153.             const unsigned long *src2, int nbits)
  154. {
  155.     if (nbits <= BITS_PER_LONG)
  156.         *dst = *src1 | *src2;
  157.     else
  158.         __bitmap_or(dst, src1, src2, nbits);
  159. }
  160.  
  161. static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
  162.             const unsigned long *src2, int nbits)
  163. {
  164.     if (nbits <= BITS_PER_LONG)
  165.         *dst = *src1 ^ *src2;
  166.     else
  167.         __bitmap_xor(dst, src1, src2, nbits);
  168. }
  169.  
  170. static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1,
  171.             const unsigned long *src2, int nbits)
  172. {
  173.     if (nbits <= BITS_PER_LONG)
  174.         *dst = *src1 & ~(*src2);
  175.     else
  176.         __bitmap_andnot(dst, src1, src2, nbits);
  177. }
  178.  
  179. static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  180.             int nbits)
  181. {
  182.     if (nbits <= BITS_PER_LONG)
  183.         *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
  184.     else
  185.         __bitmap_complement(dst, src, nbits);
  186. }
  187.  
  188. static inline int bitmap_equal(const unsigned long *src1,
  189.             const unsigned long *src2, int nbits)
  190. {
  191.     if (nbits <= BITS_PER_LONG)
  192.         return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
  193.     else
  194.         return __bitmap_equal(src1, src2, nbits);
  195. }
  196.  
  197. static inline int bitmap_intersects(const unsigned long *src1,
  198.             const unsigned long *src2, int nbits)
  199. {
  200.     if (nbits <= BITS_PER_LONG)
  201.         return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  202.     else
  203.         return __bitmap_intersects(src1, src2, nbits);
  204. }
  205.  
  206. static inline int bitmap_subset(const unsigned long *src1,
  207.             const unsigned long *src2, int nbits)
  208. {
  209.     if (nbits <= BITS_PER_LONG)
  210.         return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
  211.     else
  212.         return __bitmap_subset(src1, src2, nbits);
  213. }
  214.  
  215. static inline int bitmap_empty(const unsigned long *src, int nbits)
  216. {
  217.     if (nbits <= BITS_PER_LONG)
  218.         return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
  219.     else
  220.         return __bitmap_empty(src, nbits);
  221. }
  222.  
  223. static inline int bitmap_full(const unsigned long *src, int nbits)
  224. {
  225.     if (nbits <= BITS_PER_LONG)
  226.         return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
  227.     else
  228.         return __bitmap_full(src, nbits);
  229. }
  230.  
  231. static inline int bitmap_weight(const unsigned long *src, int nbits)
  232. {
  233.     return __bitmap_weight(src, nbits);
  234. }
  235.  
  236. static inline void bitmap_shift_right(unsigned long *dst,
  237.             const unsigned long *src, int n, int nbits)
  238. {
  239.     if (nbits <= BITS_PER_LONG)
  240.         *dst = *src >> n;
  241.     else
  242.         __bitmap_shift_right(dst, src, n, nbits);
  243. }
  244.  
  245. static inline void bitmap_shift_left(unsigned long *dst,
  246.             const unsigned long *src, int n, int nbits)
  247. {
  248.     if (nbits <= BITS_PER_LONG)
  249.         *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
  250.     else
  251.         __bitmap_shift_left(dst, src, n, nbits);
  252. }
  253.  
  254. #endif /* __ASSEMBLY__ */
  255. #endif /* __KERNEL__ */
  256. #endif /* __LINUX_BITMAP_H */
  257.